Discrete Logarithm

This note handles the construction of the discrete logarithm from its inverse function.

Theorem

Let G be a group with g∈G. Then the function f:Zord(g)→⟨g⟩ defined by

n↦gn

is an isomorphism.

This follows easily from the fact that powers up to order in group are distinct.

Given this isomorphism, a natural question to ask is what is the inverse function. In this case, we define the discrete logarithm to be exactly that.

Definition

Given an element g in a group G, we define the discrete logarithm to the base g to be a function logg:⟨g⟩→Zord(g) given by

logg⁡(a)=k

where k∈Zord(g) such that

gk=a.

Of course, using a generator (or primitive root) g we end up with an isomorphism between G and Z|G| which is much more natural to work with.

Definition

We also often call the discrete logarithm logg:G→Zn the index modulo n relative to g, and denote it by indg.

In the case of the multiplicative group of integers modulo n, we have the isomorphism:

Zφ(n)≅Un.